package medium;

import java.util.LinkedList;
import java.util.Stack;

/**
 * 331. 验证二叉树的前序序列化
 * 创建时间：2024-03-31 00:08
 * 地址：https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/description/
 */
public class 验证二叉树的前序序列化_331 {
    public static void main(String[] args) {
        Solution s = new Solution();
        s.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#");
    }
    static class Solution {
        public boolean isValidSerialization(String preorder) {
            Stack<String> stack = new Stack<>();
            String[] split = preorder.split(",");
            for (String s : split) {
                stack.push(s);
                // 当判断是叶子节点时，将叶子全部砍掉（精华）
                while(stack.size() >= 3
                        && !stack.get(stack.size() - 3).equals("#")
                        && stack.get(stack.size() - 2).equals("#")
                        && stack.get(stack.size() - 1).equals("#")) {
                    stack.pop();
                    stack.pop();
                    stack.pop();
                    stack.push("#");
                }
            }
            return stack.size() == 1 && stack.get(0).equals("#");
        }
    }
}
